package 左哥算法.ch11字符串相关;

import org.junit.Test;

import java.util.Scanner;

public class Ch01KMP算法 {

    @Test
    public void test(){
//        int[] arr = getNextArray("abaxxabadzzabaxxababe");
//        int[] arr = getNextArray("abasabaaa");
        System.out.println(strStr("mississippi","issippi"));
    }


    /**
     * kmp算法查找字符串
     */
    public static int strStr(String haystack, String needle) {
        if (needle.length()>haystack.length()){
            return -1;
        }
        if (needle.length()==0){
            return 0;
        }
        int[] nextArray = getNextArray(needle); //获取每个位置的最长公共前后缀
        int length = haystack.length();
        int i=0,j=0;
        while (i<length&&j<nextArray.length){
            if (j==-1){         //如果跳到needle的第一个之后依然无法匹配
                i++;
                j=0;
            }else if (haystack.charAt(i)==needle.charAt(j)){    //如果当前字符能够匹配，则匹配下一字符
                i++;
                j++;
            }else{
                j=nextArray[j]; //无法匹配则跳到最长公共后缀的下一位
            }
        }
        return j>=nextArray.length?i-j:-1;  //如果字符串被匹配完，则返回母字符串中第一个匹配的位置（i-j）。如果母字符串被匹配完，则返回-1
    }
    /**
     * 获取字符串每位字符的最长前后缀位数
     * 思路：
     *      1.前两位是固定死的（没有公共前后缀）
     *      2.当前位置的公共前后缀和上一位置的公共前后缀关系：
     *          如果上一位置等于它公共前后缀的下一位：则当前公共前后缀为上一位的公共前后缀+1
     *          如果上一位置不等于它公共前后缀的下一位（设它为n）：则再判断上一位是否等于n位置的公共前缀下一位,直到n跳到0位置
     */
    public static int[] getNextArray(String str){
        if (str.length()<2){
            return new int[]{-1};
        }
        int[] arr=new int[str.length()];
        arr[0]=-1;
        arr[1]=0;
        for (int i = 2; i < arr.length; i++) {
            int n=arr[i-1]; //上一个数的最长前后缀有多少个
            do{
                if (str.charAt(i-1)==str.charAt(n)){    //比较上一位与它公共前缀的下一位
                    arr[i]=n+1;
                    break;
                }
                n=arr[n];       //不同则跳到上一个数的公共前后缀的下一个位置
            }while(n!=-1);  //当比完第0个之后
        }
        return arr;
    }
}
